//leetcode 链接：
// https://leetcode.cn/problems/zigzag-conversion/description/
// 需要使用的算法：规律查找
//1、Z字形变换
string convertZ(string s, int numRows)
{
	//cout << "转换前字符串" << s << endl;
	//第一次做的思路：先把原始数据构建出来并存放起来，构建完成再遍历
	vector<string> res;
	for (int i = 0; i < numRows; i++)
	{
		res.push_back("");
	}
	int j = 0;
	int base = numRows - 2; //表示需要遍历的长度,这里很关键，多列几个就知道规律了
	//找到起点和终点：numRows,
	int start = numRows;
	int special_j = numRows - 1;
	int tmp = 0;
	for (int i = 0; i < s.length(); i++)
	{
		//处理完节点之前，检查节点得位置
		if (i == start + base)
		{
			//说明需要更换起点了
			start = start + numRows + base; //小细节这里得变动是需要加每次Z字斜线所占用得下表再加本身Z字一竖所占得下表：例如4行得时候为  4+4+2
			//重置特殊下标
			special_j = numRows - 1;
		}


		if (i >= start  && i <= start + base && numRows > 2) //小细节：边界值得处理
		{
			//如果遍历到指定范围需要特殊处理
			
			res[special_j - 1] = res[special_j - 1] + s[i];
			special_j--;
			//tmp = 1;
		}
		else
		{
			//其他情况就按照正常累加
			res[j] = res[j] + s[i];
			j++; //什么时候+1什么时候+2是需要考虑的
		//}

			if (j == numRows)
			{
				j = 0;
			}
		}


	}


	string s1 = "";
	for (int i = 0; i < res.size(); i++)
	{
		cout << res[i] << endl;
		s1 = s1 + res[i];
	}
	//cout << "转换后的字符串" <<s1<< endl;
	return s1;
}

int main()
{

	//vector<int> arr = { 32,4,-2,45,6,10,32,100,10 };
	//简单排序，双循环遍历
	//SimpleSort(arr,arr.size());
	//BublingSort(arr, arr.size());
	//QuickSort(arr, arr.size());
	//QuickSort();

	string s = convertZ("PAYPALISHIRING", 6);  //预期是PAHNAPLSIIGYIR
	return 0;
}
